moddbfandomcom-20200213-history
Haskell:Tutorials:Functions
= Functions, Currying and the true meaning of recursion = Welcome to part 2 of my Haskell tutorial. I hope you enjoyed part one so far. Functions Sets In maths, a function is an entity mapping an element of set A to an element of set B. A set is a bit difficult to define, in fact, there is no working definition for them. It's the base of all maths in the world, but it's not wholly defined, doesn't that tell you something about maths? Anyway, scientists may not have a definition for sets, but they kind of say what's a set and what's not. Int is a set in Haskell, it's the set of all whole numbers the computer can compute. Unlike other languages, which are closer to the hardware, the Int set is not bound to how many bits your processor has or anything else. The following sets are pre-defined in Haskell: * Int: Integer numbers. * Float: Decimal numbers, also known as floating point numbers. * Double: Decimal numbers of double precision. * Char: Characters. * Bool: Has only two elements: True or False * String: Not really a set, as a string in Haskell is a list of characters, but can be used like a set in functions. Apart from that, there are some other sets, like IO, Array or such weird looking sets as Maybe and Either. Function Theory A bijective function from set A to set B is an assignment. It doesn't do more than assigning an element of A to an element of B. The arithmetic term afterwards is a rule for that assignment, but you could also put every single element of A and write down what element of B it's assigned to, which could be pretty annoying, especially when dealing with infinite sets. f: \mathbb{R} \rightarrow \mathbb{R}, x \mapsto \frac{1}{x} That's a pretty neat example for a function. In Haskell, this function would be f :: Float -> Float f x = 1/x This function has a hole in it: What if x = 0 ? Panic. Mathematicians just say, it's not defined, and the computer cancels the execution of our application. But I don't want that. But look at this: \lim\limits_{n\to\infty}\frac{1}{n} = 0 So we could add f(0) = 0 to close the hole. Not correct, I know, but it's nice for showing you some Haskell concepts in functions. In math-speak, this new function looks like this: f(x) = \begin{cases} 0 & \mbox{if } x = 0 \\ \frac{1}{x} & \mbox{else} \end{cases} There are several ways we can write that in Haskell. If ... then... and else? One way is pretty obvious: We work with an if-clause. As C/C++ programmers, you should know that one all too well. In Haskell, it works more like the math-speak version. It looks like this: f :: Float -> Float f x = if x 0 then 0 else 1/x I think, if you know a bit about programming, this shouldn't give you trouble. If the value equals one, the function equals one, 1/x otherwise. The comparison operators are almost the same as in C: * ' ': Equals * '>': Greater * '<': Less * '=<': Less or equal * '>=': Greater or equal * '/=': Not equal Is there anything else to say? If so, mail me, and I will add it. Patterns Another way to tell Haskell that a function behaves differently with certain values are patterns. Here the example: f :: Float -> Float f 0 = 0 f x = 1/x Before, let me tell you that in Haskell, same function name means same function. So, here we didn't define two functions, we defined the same function for two values. Also it is important that Haskell needs the function to be unique. It can't see if you mean a function of a different type or the same. Also, the declaration doesn't have to be before it. It can also be after or way before. Thus, the order is not important as well, as always in functional languages. This is the same f :: Int -> Int f x = 1/x f 0 = 0 Well, patterns like this are a bit more restrictive than the if-then construction, because it only allows special values. But there is another kind of patterns. Guards f :: Float -> Float f x | x 0 = 0 | x /= 0 = 1/x This is equal to f :: Float -> Float f x | x 0 = 0 f x = 1/x I hope my examples are self-explanatory. It's really simple. By the way, patterns get really useful when it comes to recursion or dealing with lists. A special character in patterns is _ . It just means 'anything'. It is useful when all important values are dealt with and only one is left, and no variable for calculating is necessary. Ever used the anonymous variable in Prolog? It's just like that. Cases And the very last way to tell Haskell that we need cases are... cases. Or rather the case keyword. Here is the example: f :: Float -> Float f x = case x of 0 -> 0 y -> 1/y So you see, you have four ways to define the very same thing. Isn't Haskell nice? It lets you have it your way. Which way you use is your own decision. Patterns are the most common way, but in the end, the compiler should be able to optimize them the same way. Nested Expressions and Locals You know local variables in imperative languages, and they are really swell to work with, aren't they? Well, Haskell goes a bit further: It allows us to define local functions as well. The keyword for nested expressions is where. Here is an (not very sensible) example: cubic :: Float -> Float cubic x = x * (square x) where square x = x * x Remember, square is nested. It can only be used within the function it's nested in. Within the function, the name is to be unique, but not application-wide. But this is, in fact, one of the big strengths of Haskell. Since functions are also a type in Haskell, you can define them locally. Even better are the so called lambda-functions which allow you to generate unique functions on-the-fly (But maybe hard to write). = Tuples vs. Currying = Haskell Curry had given up both his names for this language. His first name went for the name, the other one for a concept in it. You may know what a tuple is. It's a combination of two or more elements of a set. Not even the same set. In other languages, a function that requires more than one parametre is receiving them in a tuple. As in C: int sum(int a, int b) { return a + b; } The parametre here is a tuple of two integers. There is a way to do that in Haskell as well: sum :: (Int, Int) -> Int sum (a, b) = a + b Many Haskell programmers would now say, that's not very elegant. It is correct and working, but Haskell works better by using Currying. sum :: Int -> Int -> Int sum a b = a + b This is a concept not easy to understand. I'll try slowly: Instead of working with both integers at once, Haskell takes one, evaluates the function and receives another function, like this Int -> Int. Then it evaluates this second function with the second value given. This is actually way easier than working with a tuple: A tuple is a complex datatype, a function is not. Plus, you can now do nice things likes this (in GHCi): *Main> let func = Main.sum 13 *Main> func 12 25 *Main> func 13 26 Maybe you don't see the use right now, but maybe later. Currying is a pretty simple, yet very neat concept. And as my professor said: If Mr. Curry would have lives in the 16th instead of the 20th century, we all would use it just like tuples today in maths.